#include "stdafx.h"
#include "BinaryMinHeap.h"
#include <limits> 

BinaryMinHeap::BinaryMinHeap()
{
	keyArray = new std::vector<double>();
	objectArray = new std::vector<void*>();
}

BinaryMinHeap::BinaryMinHeap(unsigned int initial_size)
{
	keyArray = new std::vector<double>(initial_size, std::numeric_limits<double>::max());
	objectArray = new std::vector<void*>(initial_size, NULL);
}

BinaryMinHeap::~BinaryMinHeap()
{
	delete keyArray;
	delete objectArray;
}

unsigned int BinaryMinHeap::size()
{
	return keyArray->size();
}

unsigned int BinaryMinHeap::get_parent_index(int index)
{
	if (index < 0) throw new std::exception("index cannot be negative in binary min heap");
	if (index == 0) return 0;
	
	return (index - 1) / 2;
}

unsigned int BinaryMinHeap::get_child_index(int index, bool isRightChild)
{
	if (index < 0) throw new std::exception("index cannot be negative in binary min heap");

	return index * 2 + 1 + (isRightChild == true);
}

void BinaryMinHeap::push(double key, void* object)
{
	keyArray->push_back(key);
	objectArray->push_back(object);

	int i = keyArray->size() - 1;
	int j = get_parent_index(i);

	while (j < i)
	{
		if (keyArray->at(j) <= keyArray->at(i))
			break;

		//swap
		double key_tmp = keyArray->at(i);
		keyArray->at(i) = keyArray->at(j);
		keyArray->at(j) = key_tmp;

		void* object_tmp = objectArray->at(i);
		objectArray->at(i) = objectArray->at(j);
		objectArray->at(j) = object_tmp;

		//goto parent
		i = j;
		j = get_parent_index(i);
	}
}

void BinaryMinHeap::pop(double& key, void*& object)
{
	unsigned int size = keyArray->size();
	if (size == 0)
		throw new std::exception("cannot pop binary min heap when it is empty");

	key = keyArray->at(0);
	object = objectArray->at(0);
	keyArray->at(0) = keyArray->at(size - 1);
	objectArray->at(0) = objectArray->at(size - 1);

	keyArray->pop_back();
	objectArray->pop_back();

	size = keyArray->size();

	if (size == 0)
		return;

	unsigned int i = 0;
	unsigned int last_idx = size - 1;
	while (i < last_idx)
	{
		unsigned int child_idx = get_child_index(i, false);
		if (child_idx > last_idx)
			break;
		unsigned int child_idx_tmp = get_child_index(i, true);
		if (child_idx_tmp <= last_idx)
			if (keyArray->at(child_idx) > keyArray->at(child_idx_tmp))
				child_idx = child_idx_tmp;
		if (keyArray->at(i) <= keyArray->at(child_idx))
			break;

		// swap
		double key_tmp = keyArray->at(i);
		keyArray->at(i) = keyArray->at(child_idx);
		keyArray->at(child_idx) = key_tmp;
		void* object_tmp = objectArray->at(i);
		objectArray->at(i) = objectArray->at(child_idx);
		objectArray->at(child_idx) = object_tmp;

		// goto child
		i = child_idx;
	}
}